import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class project {
    List<List<Integer>> list=new ArrayList<>();
    Deque<Integer> deque=new ArrayDeque<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if(root==null){
            return list;
        }
        dfs(root,targetSum);
        return list;
    }
    public void dfs(TreeNode root,int sum){
        if(root==null){
            return ;
        }
        deque.addLast(root.val);
        sum-=root.val;
        if(root.left==null&&root.right==null&&sum==0){
            list.add(new ArrayList<>(deque));
        }
        dfs(root.left,sum);
        dfs(root.right,sum);
        deque.pollLast();
    }















    public int longestValidParentheses(String s) {
        Stack<Integer> stack=new Stack<>();
        int max=0;
        stack.push(-1);
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(ch=='('){
                stack.add(i);
            }else{
                stack.pop();
                if(stack.isEmpty()){
                    stack.push(i);
                }else{
                    max=Math.max(max,i-stack.peek());
                }
            }
        }
        return max;
    }












    public int trap(int[] height) {
        int left=0;
        int right=height.length-1;
        int leftmax=0;
        int rightmax=0;
        int ret=0;
        while (left<right){
            leftmax=Math.max(leftmax,height[left]);
            rightmax=Math.max(rightmax,height[right]);
            if(height[left]<height[right]){
                ret+=leftmax-height[left];
                left++;
            }else{
                ret+=rightmax-height[right];
                right--;
            }
        }
        return ret;
    }














        public int[][] merge(int[][] intervals) {
            int len=intervals.length;
            if(len==0){
                return new int[0][2];
            }
            Arrays.sort(intervals, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0]-o2[0];
                }
            });
            List<int[]> list=new ArrayList<>();
            for(int i=0;i<len;i++){
                int a=intervals[i][0];
                int b=intervals[i][1];
                if(list.size()==0||list.get(list.size()-1)[1]<a){
                    list.add(new int[]{a,b});
                }else{
                    list.get(list.size()-1)[1]=Math.max(b,list.get(list.size()-1)[1]);
                }
            }
            return list.toArray(new int[list.size()][]);
        }

















    public int search(int[] nums, int target) {
        int len=nums.length;
        if(len==0){
            return -1;
        }
        if(len==1){
            return nums[0]==target?0:-1;
        }
        int left=0;
        int right=len-1;
        while (left<=right){
            int mid=(left+right)/2;
            if(nums[mid]==target){
                return mid;
            }
            if(nums[0]<=nums[mid]){
                if(nums[0]<=target&&target<nums[mid]){
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }else{
                if(target<=nums[len-1]&&nums[mid]<target){
                    left=mid+1;
                }else{
                    right=mid-1;
                }
            }
        }
        return -1;
    }
}
